package Tree;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-07-18
 * Time: 15:11
 */
public class BinaryTree {
    static class TreeNode {
        public char val;
        public TreeNode left;//储存左孩子的引用
        public TreeNode right;//储存右孩子的引用


        public TreeNode(char val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    '}';
        }
    }

    //创建二叉树：
    //遍历字符串的全局变量，局部变量递归时会把i置0
    public static int i = 0;
    public static TreeNode createTree(String str) {
        TreeNode root = null;
        if(str.charAt(i) != '#') {
            //先创建一个根节点
            root = new TreeNode(str.charAt(i));

            //创建好根，i往后走，创建左右子树的各个节点
            i++;

            root.left = createTree(str);
            root.right = createTree(str);

        }else {
            i++;
        }

        return root;
    }

    // 前序遍历（非递归实现）
    public void preOrderNor(TreeNode root) {
        if (root == null) {
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                //根节点开始要放入栈中
                cur = stack.push(cur);
                System.out.print(cur.val +" ");
                cur = cur.left;
            }

            //cur == null，就把栈里的元素，拿到top引用中
            TreeNode top = stack.pop();

            //cur再走top的右边
            cur = top.right;
        }

    }


    // 前序遍历
   public void preOrder(TreeNode root) {
        //结束条件
        if (root == null) {
            return;
        }

        //相当于递推公式：根 左树 右树
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }


    //子问题思路前序遍历
    List preOrder2(TreeNode root) {
        //定义一个顺序表，每次递归，把递归的返回值放入顺序表
        List<Character> list = new ArrayList<>();
        //结束条件
        if (root == null) {
            return list;
        }

        list.add(root.val);

        List<Character> leftTree = preOrder2(root.left);
        list.addAll(leftTree);//返回时，把前一个左树放入顺序表中

        List<Character> rightTree = preOrder2(root.right);
        list.addAll(rightTree);//返回时，把前一个右树放入顺序表中

        return list;
    }

    // 中序遍历
    void inOrder(TreeNode root) {

        //结束条件
        if (root == null) {
            return;
        }

        //相当于递推公式：左树 根 右树
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }


    // 中序遍历（非递归实现）
    public void inOrderNor(TreeNode root) {
        if (root == null) {
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                //根节点开始要放入栈中
                cur = stack.push(cur);
                cur = cur.left;
            }

            //cur == null，就把栈里的元素，拿到top引用中
            TreeNode top = stack.pop();
            System.out.print(top.val +" ");
            //cur再走top的右边
            cur = top.right;
        }

    }


    //中序遍历（非递归实现）：利用返回值
    public List<Character> inorderTraversal(TreeNode root) {

        List<Character> list =  new ArrayList<>();

        if(root == null) {
            return list;
        }

        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();


        while(cur != null || !stack.isEmpty()) {

            while(cur != null) {
                cur = stack.push(cur);
                cur = cur.left;
            }

            //cur == null，就把栈里的元素，拿到top引用中
            TreeNode top = stack.pop();
            list.add(top.val);
            //cur再走top的右边
            cur = top.right;

        }

        return list;
    }



    // 后序遍历
    void postOrder(TreeNode root) {

        //结束条件
        if (root == null) {
            return;
        }

        //相当于递推公式： 右树 左树 根
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

   public void postOrderNor(TreeNode root) {

        //结束条件
        if (root == null) {
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

       //prev负责记录被打印过的结点
        TreeNode prev = null;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            TreeNode top = stack.peek();
            if (top.right == null || top.right == prev) {
                System.out.print(top.val + " ");
                stack.pop();

                prev = top;//prev负责记录被打印过的结点
            }else {
                cur = top.right;
            }
        }
    }


    //遍历二叉树获得节点个数
    public static int nodeSize;
    public void size(TreeNode root) {
        if (root == null) {
            return;
        }

        nodeSize++;

        //递归遍历
        size(root.left);
        size(root.right);

    }


    //子问题思路二叉树获得节点个数
    //方法：左子树节点 + 右子树节点 + 1; '1'为概树第1个根节点
    public int size2(TreeNode root) {
        if (root == null) {
            return 0;
        }

        //树不为空，左子树节点 + 右子树节点 + 1
        return  size2(root.left) +
                size2(root.right) + 1;

    }


    //获取叶子节点个数
    //遍历方法
    public static int NodeCount;
    public void getLeafNodeCount(TreeNode root) {
        if (root == null) {
            return;
        }

        //节点左右两节点都为null时，就是叶子结点
        if (root.left == null && root.right == null) {
            NodeCount++;
        }

        //有一边树不为空就递归遍历
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);

    }


    //子问题方法
    public int getLeafNodeCount2(TreeNode root) {
        if (root == null) {
            return 0;
        }

        //节点左右两节点都为null时，就是叶子结点
        if (root.left == null && root.right == null) {
            return 1;
        }

        //方法:递归的方式，左叶子节点 + 右叶子节点
        /*
         这里递归时，满足叶子节点就会，return 上面的 1 给这个递归函数，最后返回叶子节点个数
         */
       return getLeafNodeCount2(root.left) +
               getLeafNodeCount2(root.right);
    }


    //求第K层节点树
    /** 子问题方法：左边第k-1节点，加右边第K-1结点；
     *            因为二叉树每遍历一层就会，往下走一层，就是k的值就 减一
     *             当k1==1时就到了第K层
     */

    public int getKLeveNodeCount(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }

        //返回条件是，k == 1就到了第K层；返回节点数
        if (k == 1) {
            return 1;
        }


        return getKLeveNodeCount(root.left, k-1) +
                getKLeveNodeCount(root.right, k-1);
    }


    /**时间复杂度O (N)，因为要遍历二叉树
     * 空间复杂度O (logN),以2为底，N次方，二叉树整体左树遍历完，内存会被回收，所以二叉树左右树，最高那边的树，就是空间复杂度
     *
     * 二叉树的高度：公式：（左树高度 和 右树高度）.的最大值 + 1；
     * @param root
     * @return
     */
    public  int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }

        //递归遍历左右树高度，遍历到root == null，再返回
        int leftTreeHeight = getHeight(root.left);
        int rightTreeHeight = getHeight(root.right);

        return Math.max(leftTreeHeight, rightTreeHeight) + 1;
    }


    /**
     * 时间复杂度O (N)
     *空间复杂度O (logN),以2为底
     *
     * 找到指定的val树
     * @param root
     * @param val
     * @return
     */
    public TreeNode findVal(TreeNode root, char val) {
        if (root == null) {
            return null;
        }

        //返回的条件是，找到val树。

        //根遍历
        if (root.val == val) {
            return root;
        }

        //遍历左树,找val
        TreeNode leftT = findVal(root.left, val);
        if (leftT != null) {
            return leftT;
        }

        //遍历右树,找val
        TreeNode rightT = findVal(root.right, val);
        if (rightT != null) {
            return rightT;
        }

        return null;
    }



    //层序遍历
   public void levelOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();

        //先把根节点放入队列
        queue.offer(root);

        while (!queue.isEmpty()) {
            //弹出去给，cur
            TreeNode cur = queue.poll();
            System.out.print(cur.val +" ");

            if (cur.left != null) {
                queue.offer(cur.left);
            }

            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }

    }

    //二叉树的层序遍历
    public List<List<Character>> levelOrder2(TreeNode root) {
        List<List<Character>> ret = new ArrayList<>();

        if (root == null) {
            return ret;
        }

        Queue<TreeNode> queue = new LinkedList<>();

        //先把根节点放入队列
        queue.offer(root);

        while (!queue.isEmpty()) {
            List<Character> list = new ArrayList<>();

            //定义放在这里，等二叉树走完一层，才更新另外一层的size
            int size = queue.size();

            while(size != 0) {

                TreeNode cur = queue.poll();
                list.add(cur.val);

                if (cur.left != null) {
                    queue.offer(cur.left);
                }

                if (cur.right != null) {
                    queue.offer(cur.right);
                }
                size--;

            }

            //一维数组走完一个放入二维数组一个
            ret.add(list);
        }

        return ret;
    }


    /**方法：
     * 可以先从根顺着层序遍历
     * 然后翻入，二维数组时：每次都把一维数组，头插（addFirst），
     *  达到,从尾巴开始层序遍历
     * @param root
     * @return
     */

    public LinkedList<LinkedList<Character>> levelOrder3(TreeNode root) {
        LinkedList<LinkedList<Character>> ret = new LinkedList<>();

        if (root == null) {
            return ret;
        }

        Queue<TreeNode> queue = new LinkedList<>();

        //先把根节点放入队列
        queue.offer(root);

        while (!queue.isEmpty()) {
            List<Character> list = new LinkedList<>();

            //定义放在这里，等二叉树走完一层，才更新另外一层的size
            int size = queue.size();

            while(size != 0) {

                TreeNode cur = queue.poll();
                list.add(cur.val);

                if (cur.left != null) {
                    queue.offer(cur.left);
                }

                if (cur.right != null) {
                    queue.offer(cur.right);
                }
                size--;

            }

            //一维数组走完一个放入二维数组一个,
            // 但是每次都把一维数组，头插（addFirst）
            ret.addFirst((LinkedList<Character>) list);
        }

        return ret;
    }




    //判断一棵树是不是完全二叉树
   public boolean isCompleteTree(TreeNode root) {

        //空节点也是完全二叉树
        if (root == null) {
            return true;
        }

       Queue<TreeNode> queue = new LinkedList<>();
       queue.offer(root);

       while (!queue.isEmpty()) {
           TreeNode cur = queue.poll();

           //空节点也放进去
           if (cur != null) {
               queue.offer(cur.left);
               queue.offer(cur.right);
           }else {
               break;
           }
       }

       while (!queue.isEmpty()) {
          TreeNode peek = queue.peek();

          //注意这里的null，是队列里的元素是“null”，不是队列为空
          if (peek != null) {
              return false;
          }
          //可以全部弹完，说明队列里就只有 null 元素.就是完全二叉树
          queue.poll();

       }
       return true;
   }


   //最近公共祖先,方法一 ：
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }

        if(root == p || root == q) {
            return root;
        }


        TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
        TreeNode rightTree = lowestCommonAncestor(root.right,p,q);

        if(leftTree != null && rightTree != null) {
            return root;
        }else if(leftTree != null && rightTree == null) {
            return leftTree;
        }else {
            return rightTree;
        }
    }



    //最近公共祖先,方法二 ：
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {


        Stack<TreeNode> stackP = new Stack<>();
        Stack<TreeNode> stackQ = new Stack<>();

        //1.把元素存入栈中
        getPath(root, p,stackP);
        getPath(root, q,stackQ);


        //2.求出那个栈元素多，让多的先出栈，直到两个栈元素一样多
        int sizeP = stackP.size();
        int sizeQ = stackQ.size();

        if (sizeP > sizeQ) {
            int size = sizeP - sizeQ;
            //元素多的栈先走出栈，他们的差值元素个数
            while (size != 0) {
                stackP.pop();
                size--;
            }
        }else {
            int size = sizeQ - sizeP;
            while (size != 0) {
                stackQ.pop();
                size--;
            }
        }


        //看看栈顶元素，是否相等不相等就弹出，相等则就是最近祖先
        while (!stackP.isEmpty() && !stackQ.isEmpty()) {

            //stackP == stackQ，比较节点，如果比较的值是Integer类型,超过一定范围就要无效，要用equals比较
            if ( stackQ.peek() == stackP.peek()) {
                return stackP.peek();
            }else {
                //元素不一样就出栈
                stackP.pop();
                stackQ.pop();
            }
        }

        return null;
    }


    /**
     *
     * @param root
     * @param node:要找路径的q p 节点
     * @param stack:存放节点的栈
     */
    //获取q, p路径
    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
        if (root == null) {
            return false;
        }
        //节点放入栈中
        stack.push(root);

        //找到返回true
        if (root == node) {
            return true;
        }

        //递归找q, p, 递归返回值ret
       boolean ret = getPath(root.left,node,stack);
        //一层一层往上走
        if (ret) {
            return true;
        }

        ret = getPath(root.right,node,stack);
        if (ret) {
            return true;
        }

        //左右树遍历完没有找到,就把不是该路径的，节点弹出栈，并返回false
        stack.pop();
        return false;

    }

}
